package leetCode.solution;

import java.util.ArrayList;
import java.util.LinkedList;
import java.util.List;
import java.util.Random;
import java.util.stream.Stream;

import com.alibaba.fastjson.JSON;

public class Solution102 {

	public static class TreeNode {
		int val;
		TreeNode left;
		TreeNode right;

		TreeNode() {
		}

		TreeNode(int val) {
			this.val = val;
		}

		TreeNode(int val, TreeNode left, TreeNode right) {
			this.val = val;
			this.left = left;
			this.right = right;
		}
	}
	
	public static void main(String[] args) {
		TreeNode node1 = new TreeNode(3, new TreeNode(9), new TreeNode(20, new TreeNode(15), new TreeNode(7)));
		System.out.println(JSON.toJSONString(new Solution102().new Solution().levelOrder(node1)));
		System.out.println(JSON.toJSONString(new Solution102().new Solution().levelOrder1(node1)));
	}

	class Solution {
		public List<List<Integer>> levelOrder(TreeNode root) {
			List<List<Integer>> res = new ArrayList();
			LinkedList<TreeNode> queue = new LinkedList();
			if (root != null) {
				queue.offerLast(root);
			}
			while (!queue.isEmpty()) {
				List<Integer> list = new ArrayList();
				int n = queue.size();
				for (int i = 0; i < n; i++) {
					TreeNode curNode = queue.pollFirst();
					list.add(curNode.val);
					if (curNode.left != null) {
						queue.offerLast(curNode.left);
					}
					if (curNode.right != null) {
						queue.offerLast(curNode.right);
					}
				}
				res.add(list);
			}
			return res;
		}

		public List<List<Integer>> levelOrder1(TreeNode root) {
			List<List<Integer>> res = new ArrayList();
			LinkedList<TreeNode> queue = new LinkedList();
			if (root != null) {
				queue.offerLast(root);
			}
			while (!queue.isEmpty()) {
				int n = queue.size();
				List<Integer> list = new ArrayList();
				for (int i = 0; i < n; i++) {
					TreeNode node = queue.pollFirst();
					list.add(node.val);
					if (node.left != null) {
						queue.offerLast(node.left);
					}
					if (node.right != null) {
						queue.offerLast(node.right);
					}
				}
				res.add(0, list);
			}
			return res;
		}
	}
}
